package sort.test3_30;

import java.util.Arrays;

public class RadixSort1 {

    public  void sort(int[] nums){
        if (nums.length==0){
            return;
        }
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
        max=Math.max(max,nums[i]);
        }
        int exp;
        for ( exp = 1; max/exp>0 ; exp*=10) {
            countSort(nums,exp);
        }
    }

    //  CKG TODO 2023/3/30: 　关键是确定桶的大小　已经确定必须是１０　然后是每个元素的数值　必须放在哪里
//
    public   void countSort(int[] nums,int exp){

        int[] countArray = new int[10];
        int[] output=new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            countArray[(nums[i]/exp)%10]++;
        }

        for (int i = 1; i < 10; i++) {
            countArray[i]=countArray[i-1]+countArray[i];
        }
//  CKG TODO 2023/3/30:  由于计数排序是每个桶位只有一个数字　所以不存在一个桶位置有多个数字　下面的方法在这里不适用　
//        for (int i = 0; i < nums.length; i++) {
//            output[--countArray[(nums[i]/exp)%10]]=nums[i];
//        }
//
//        for (int i = 0; i < output.length; i++) {
//            nums[i]=output[i];
//        }

        // 将数据存储到临时数组output[]中
        for (int i = nums.length - 1; i >= 0; i--) {
            output[countArray[(nums[i] / exp) % 10] - 1] = nums[i];
            countArray[(nums[i] / exp) % 10]--;
        }



        // 将排序好的数据赋值给a[]
        for (int i = 0; i < nums.length; i++)
            nums[i] = output[i];


        output=null;
        countArray=null;
    }

    public static void main(String[] args) {

        RadixSort1 radixSort1 = new RadixSort1();
        int[] arr = {3,44,38,5,47};
        radixSort1.sort(arr);
        System.out.println(Arrays.toString(arr));

    }




}
